package main


func topKFrequent(nums []int, k int) []int {
	countMap := make(map[int]int)
	for _, v := range nums {
		countMap[v]++
	}
	result := make([][2]int, 0, k+1)
	for num, count := range countMap {
		index := findIndex(result, count)
		result = append(result, [2]int{0,0})
		copy(result[index+1:], result[index:])
		result[index] = [2]int{num, count}
		if len(result) > k {
			result = result[:k]
		}
	}
	ret := make([]int, 0, k)
	for _, pair := range result {
		ret = append(ret, pair[0])
	}
	return ret
}

func findIndex(arr [][2]int, count int) int {
	i := 0
	j := len(arr)-1
	for i <= j {
		mid := (i+j)/2
		if arr[mid][1] <= count {
			j = mid - 1
		} else {
			i = mid + 1
		}
	}
	return i
}

func main() {
	ret := topKFrequent([]int{1,1,1,2,2,2,3,4}, 2)
	println(ret)
}